package com.kizuki.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 *
 * https://leetcode-cn.com/problems/n-queens/
 */
public class N皇后 {

    class Solution {

        List<List<String>> res = new ArrayList<>();

        public List<List<String>> solveNQueens(int n) {
            char[][] board = new char[n][n];
            for (char[] chars : board) {
                Arrays.fill(chars, '.');
            }
            backtrack(board, 0);
            return res;
        }

        List<String> convert(char[][] board){
            List<String> strs = new ArrayList<>();
            for (char[] chars : board) {
                strs.add(String.copyValueOf(chars));
            }
            return strs;
        }

        void backtrack(char[][] board, int row){
            if (row == board.length) {
                res.add(convert(board));
                return;
            }
            int colLen = board.length;
            for (int i = 0; i < colLen; i++) {
                if (!check(board, row, i)) {
                    continue;
                }
                board[row][i] = 'Q';
                backtrack(board, row + 1);
                board[row][i] = '.';
            }
        }

        boolean check(char[][] board, int row, int col) {
            int len = board.length;
            for (int i = 0; i < row; i++) { // row
                if (board[i][col] == 'Q') return false;
            }
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { // 左上
                if (board[i][j] == 'Q') return false;
            }
            for (int i = row - 1, j = col + 1; i >= 0 && j < len; i--, j++) { // 右上
                if (board[i][j] == 'Q') return false;
            }
            return true;
        }
    }

}
